#include "stack_queue.h"

//listNode初始化
listNode::listNode() { data = 0; next = NULL; }
listNode::listNode(int nodeData, listNode* succ) {
    data = nodeData; next = succ;
}

//stack初始化
MyStack::MyStack() {
    topNode = new listNode;
    stackSize = 0;
}
//销毁栈
MyStack::~MyStack(){
    for (int i = 0; i < stackSize; i++)
    {
        listNode* p = topNode;
        topNode = topNode->next;
        delete p; p = NULL;
    }
    stackSize = 0;
}
//入栈
bool MyStack::push(const int&n) {
    if (stackSize == 0) {
        topNode = new listNode;
        topNode->data = n;
        stackSize++;
    }
    else {
        listNode* p = new listNode(n);
        p->next = topNode;
        topNode = p;
        stackSize++;
    }
    return 1;
}

//出栈
bool MyStack::pop(int& data) {
    if (stackSize == 0)return 0;
    listNode* p = topNode; data = p->data;
    topNode = topNode->next; stackSize--;
    delete p; p = NULL;
    return 1;
}

//返回栈顶元素
bool MyStack::getTop(int& data) {
    if (stackSize == 0)return 0;
    data = topNode->data;
    return 1;
}
//判断栈是否为空
/*bool MyStack::empty() {
    if (stackSize == 0)return 1;
    else return 0;
}*/
//输出栈
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

//初始化队列
MyQueue::MyQueue(const int& maxSize) {
    queue = new int;
    capacity = maxSize;
    front = rear = 0;
}
//销毁队列
MyQueue::~MyQueue() {
    front = rear = 0;
}
//入队
bool MyQueue::enQueue(const int& newData) {
    if ((rear+1) % capacity==front)return 0;
    queue[rear] = newData;
    rear = (rear + 1) % capacity;
    return 1;
}
//出队
bool MyQueue::deQueue(int& data) {
    if (rear == front)return 0;
    data = queue[front];
    front = (front + 1) % capacity;
    return 1;
}
//返回队头元素
bool MyQueue::getFront(int&val) {
    if (rear == front)return 0;
    val = queue[front];
    return 1;
}
//判断队列是否为空
bool MyQueue::isFull() {
    if ((rear + 1) % capacity == front)return 1;
    else return 0;
}
//打印队列
void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}
//中缀式转后缀式
bool postfixExpression(const string&str, string& result) {
    MyStack S;
    bool judge = 1, j = 0;
    int l = 0, r = 0, y;
    for (int i = 0; i < str.size(); i++)
    {
        if (j == 0)
            if (str[i] >= 48 && str[i] < 58)j = 1;
            else if (str[i] == '(')l++;
            else {
                judge = 0; break;
            }
        else {
            if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')j = 0;
            else if (str[i] == ')')r++;
            else {
                judge = 0; break;
            }
        }
        if (r > l)judge = 0;
    }
    if (!judge|| r != l||j==0){
        result = "Expression is wrong!";
        return 0;
    }
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] >= 48 && str[i] < 58) {
            result.push_back(str[i]); 
        }
        else {
            int x = 0;
            switch (str[i])
            {
            case '+':x = 1; break;
            case '-':x = 2; break;
            case '*':x = 3; break;
            case '/':x = 4; break;
            case '(':x = 0; break;
            case ')':x = 6; break;
            default:judge = 0;
                break;
            }

            if (x == 0) {
                S.push(x); continue;
            }
            
            while (S.getTop(y) &&(((y+1)/2>=(x+1)/2)||(x==6&&y!=0)))
            {
                
                switch (y)
                {
                case 1:result.push_back('+'); break;
                case 2:result.push_back('-'); break;
                case 3:result.push_back('*'); break;
                case 4:result.push_back('/'); break;
                }
             
                S.pop(y);
                if (y == 5)break;
            }
           if (x == 6 && y == 0)S.pop(y);
           if(x!=6)S.push(x);
        }
    }

    while (S.getTop(y)) {
        switch (y)
        {
        case 1:result.push_back('+'); break;
        case 2:result.push_back('-'); break;
        case 3:result.push_back('*'); break;
        case 4:result.push_back('/'); break;
        }
        S.pop(y);
    }
    return 1;
}
//计算表达式
bool expressionVal(const string& st1, int& result)
{
    string st2;
    
    if (!postfixExpression(st1, st2)) {
        result = 0;
        return 0;
    }
    MyStack S;
    for (int i = 0; i < st2.size(); i++)
    {
        
        if (st2[i] >= 48 && st2[i] < 58)
            S.push(st2[i] - 48);
        else {
            int x, y;
            S.pop(x); S.pop(y);
            switch (st2[i])
            {
            case '+':result = x + y; break;
            case '-':result = y - x; break;
            case '*':result = x * y; break;
            case '/':result = y / x; break;
            }
            S.push(result);
        }
    }
    return 1;
}

//输出杨辉三角
void yanghui(const int&num) 
{
    if (num == 0)return;
    MyQueue Q(2 + num);
    Q.enQueue(1); Q.enQueue(1);
    Q.printQueue();
    for (int i = 1; i < num; i++)
    {
        MyQueue Q2(2 + num); Q2.enQueue(1);
        int x, y;
        while (Q.deQueue(x))
        {
            y = 0;
            Q.getFront(y);
            Q2.enQueue(x + y);
        }
        Q2.printQueue();
        Q = Q2;
    }
}